package DP.背包.每样无限;

import org.junit.Test;

/**
 * 思路：
 *      无限个 -> 拿后, 选择范围 preNum不缩
 *
 *      背包问题 第二个参数
 *          纯背包问题 -> 最多拿x
 *                          纯背包 给你N个 val最大 -> N个 必 (全/恰好) 用完
 *                          所以 也是 curSum
 *                          ->dp[n][m] 前n个 当前已装m个 的 最大val
 *
 *          min找零钱 -> curSum
 *
 *        最终 -> now_cS 当前的curSum
 *
 */
/**
 * min/max 初0
 *
 *
 * 无限个 -> 不可能时 的 个数n+1:
 *                            应该是 全用1元凑 = 总钱数+1
 *                            不是 币种类数+1
 *
 * 外部初始化
 *      for [0][j] = xx -> i=0 已经算完
 *
 *      -> dp时 for[1起][]
 *
 *
 * 极易少：
 *      dp[0][0] = 0; // 可能
 *
 *
 */
public class 零钱兑换322_每样无限_最少几个币_dp纯净版 {
    public int coinChange(int[] coins, int amount){
        int n = coins.length;
        int[][] dp = new int[n+1][amount+1];

        // 处理 [0][] [][0] 不可能的那个
        for (int pN = 0; pN < dp.length; pN++) {
            for (int now_cS = 0; now_cS < dp[0].length; now_cS++) {
                if(pN==0){
                    if(now_cS==0){
                        dp[0][0] = 0; // 可能 【易少点】
                    }else {
                        dp[0][now_cS] = amount+1; // 不可能
                    }
                    continue;
                }
            }
        }

        // 11
        for (int pN = 1; pN <= coins.length; pN++) {
            for (int zhenghao_cS = 1; zhenghao_cS <= amount; zhenghao_cS++) {
                int cI = pN - 1;
                if(zhenghao_cS - coins[cI] >= 0){
                    // 无限个 -> 拿后, 选择范围 不缩
                    int na = dp[pN][zhenghao_cS-coins[cI]] + 1;
                    // [很好想的] 就任性 就不拿
                    int buna = dp[pN-1][zhenghao_cS];
                    dp[pN][zhenghao_cS] = Math.min(na,buna);
                }
                // [很好想的] 拿了就超了! -> 肯定不能拿
                else {
                    int buna = dp[pN-1][zhenghao_cS];
                    dp[pN][zhenghao_cS] = buna;
                }
            }
        }
        return dp[coins.length][amount] == amount+1 ? -1: dp[coins.length][amount];
    }

    @Test
    public void test() {
        int[] p = {1,2,5};
        int a = 11;
        System.out.println("RES:" + coinChange(p, a));
    }
}
